//
// Created by lanlu on 2025/8/7.
//

#include <vector>
#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr){}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr){}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right){}
};

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        // 递归出口
        if (preorder.empty())
        {
            // 如果切分后的数组为空，说明走到叶子节点，返回
            return nullptr;
        }

        // 根据前序遍历的第一个元素 创建根节点
        int rootVal = preorder[0];
        TreeNode *root = new TreeNode(rootVal);
        // 查找根节点在中序遍历中的位置
        auto it = find(inorder.begin(), inorder.end(), rootVal);
        // 计算左子树的节点个数
        int leftSize = it - inorder.begin();

        // 切分左子树的前序和中序遍历结果 递归创建左子树
        // 这里通过左闭右开的方式来截取数组
        vector<int> leftPreorder(preorder.begin() + 1, preorder.begin() + 1 + leftSize);
        vector<int> leftInorder(inorder.begin(), it);
        root->left = buildTree(leftPreorder, leftInorder);

        // 切分右子树的前序和中序遍历结果 递归创建右子树
        vector<int> rightPreorder(preorder.begin() + 1 + leftSize, preorder.end());
        vector<int> rightInorder(it + 1, inorder.end());
        root->right = buildTree(rightPreorder, rightInorder);

        return root;
    }
};